#include <bits/stdc++.h>
using namespace std;

// 【题目】力扣70. 爬楼梯
// 【难度】简单
// 【提交】2025.10.21 https://leetcode.cn/problems/climbing-stairs/submissions/672439203/
// 【标签】动态规划；数学
class Solution {
public:
    int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        int a = 1;
        int b = 2;
        for(int i = 3; i < n + 1; ++i) {
            int c = a + b;
            a = b;
            b = c;
        }
        return b;
    }
};

/**
 * @brief 学习总结：
 * 一、题意与模型
 * 假设你正在爬楼梯，需要n阶才能到达楼顶。
 * 每次可以爬1或2个台阶，问有多少种不同的方法可以爬到楼顶。
 * 模型：动态规划（斐波那契数列），通过状态转移方程求解。
 * 
 * 二、标准解法状态设计
 * 设dp[i]表示到达第i阶楼梯的方法数，则有：
 * dp[i] = dp[i-1] + dp[i-2]
 * 初始状态：dp[1] = 1, dp[2] = 2
 * 由于只需要前两个状态，可以使用滚动数组优化空间复杂度。
 * 
 * 三、你的实现思路
 * 使用动态规划思想，通过滚动数组优化空间复杂度。
 * 只保存前两个状态a和b，在循环中不断更新。
 * 
 * 四、逐行注释（带细节提醒）
 * if(n == 1) return 1; // 只有1阶，只有1种方法
 * if(n == 2) return 2; // 有2阶，有2种方法（1+1或2）
 * 
 * int a = 1; // 初始化：到达第1阶的方法数
 * int b = 2; // 初始化：到达第2阶的方法数
 * 
 * for(int i = 3; i < n + 1; ++i) { // 从第3阶计算到第n阶
 *     int c = a + b; // 当前阶的方法数等于前两阶方法数之和
 *     a = b;         // 更新a为前一阶的方法数
 *     b = c;         // 更新b为当前阶的方法数
 * }
 * return b; // 返回到达第n阶的方法数
 * 
 * 五、正确性证明
 * 算法基于斐波那契数列的性质：
 * 到达第i阶楼梯的方法数 = 到达第i-1阶的方法数（再爬1阶）+ 到达第i-2阶的方法数（再爬2阶）
 * 通过数学归纳法可以证明该递推关系的正确性。
 * 
 * 六、复杂度
 * 时间：O(n)，需要循环n-2次。
 * 空间：O(1)，只使用了常数级别的额外空间。
 * 
 * 七、优缺点分析
 * 优点：
 *   - 时间复杂度低，只需线性时间；
 *   - 空间复杂度低，使用滚动数组优化；
 *   - 代码简洁，实现高效。
 * 缺点：
 *   - 对于非常大的n，可能存在整数溢出问题；
 *   - 无法直接获取所有可能的爬楼梯方案。
 * 
 * 八、改进建议
 * 1. 可以添加输入验证：if (n <= 0) return 0;
 * 2. 可以使用矩阵快速幂将时间复杂度优化到O(log n)；
 * 3. 对于教学场景，可以添加注释解释状态转移方程的推导过程。
 * 
 * 九、一句话总结
 * 通过动态规划和滚动数组优化，你的实现高效地解决了爬楼梯问题，
 * 展现了基础动态规划问题的经典解法。
 */